package 每日一题;

import java.util.ArrayList;
import java.util.HashMap;

public class T2008_出租车的最大盈利 {

    /**
     *解决的问题是从1到n 最多赚多少钱
     * 定义dfs(i) 表示从1到n最多可以赚多少钱
     * 如果没有人从i下车 那问题就变成了 从1到i-1最多可以赚多少钱
     * 即 dfs(i)  = dfs(i-1)
     *
     * 如果至少有一位乘客 在i下车 我们可以枚举载哪位乘客 取其中最赚钱的方案即
     * dfs(i) = max{ dfs(start)+i-start+tip}
     *
     * 这两种情况取最大值 就得到了dfs(i)
     *
     * dfs(i) = MAX(dfs(i-1), max{dfs(start)+i-start+tip})
     *
     * 递归边界 dfs(1)  = 0 没有在1下车的乘客
     *
     * 递归入口 dfs(n)
     *
     * 完整解析
     *https://leetcode.cn/problems/maximum-earnings-from-taxi/solutions/2558504/jiao-ni-yi-bu-bu-si-kao-dong-tai-gui-hua-k15a/?envType=daily-question&envId=2023-12-08
     */
    HashMap<Integer, ArrayList<int[]>> end_map;

    //增加缓存 默认值设置为null ,不等于null 说明已经计算到值了 直接用就行
    Long[] cache;
    public long maxTaxiEarnings(int n, int[][] rides) {
        end_map = new HashMap<>();
        cache = new Long[n+1];

        cache[1] = 0L;

        for (int[] ride : rides) {
            ArrayList<int[]> list = end_map.getOrDefault(ride[1], new ArrayList<>());
            list.add(ride);
            end_map.put(ride[1],list);
        }

        return dfs(n);
    }

    public long  dfs(int n){


        //查到缓存 缓存里有 n=1 的返回值  所以这里不用写递归结束条件
        if (cache[n]!=null){
            return cache[n];
        }

        //没乘客上车
        long ans = dfs(n-1);

        //依次算出每个乘客上车 获得的收益
        if (end_map.containsKey(n)){
            //遍历 所有在n下车的乘客
            ArrayList<int[]> list = end_map.get(n);
            for (int[] ride : list) {
                int v = ride[1] - ride[0] + ride[2];
                ans = Math.max(ans,dfs(ride[0])+v);
            }

        }
        //结果存入缓存
        cache[n] = ans;
        return ans;
    }

}
